home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 6 / CU Amiga Magazine's Super CD-ROM 06 (1996)(EMAP Images)(GB)(Track 1 of 4)[!][issue 1997-01].iso / cucd / online / fidonetts / fsc-0060.001 < prev    next >
Text File  |  1992-03-08  |  7KB  |  218 lines
  1. Document: FSC-0060
  2. Version:  001
  3. Date:     08-Mar-1992
  4.  
  5.  
  6.  
  7.  
  8.                         Calculation and Usage of CRC's
  9.                              Frank van der Loos
  10.                                  2:285/305.4         
  11.  
  12.  
  13.  
  14.  
  15. Status of this document:
  16.  
  17.      This FSC contains information of value to the general FidoNet(r)
  18.      community.  Distribution of this document is unlimited.
  19.  
  20.      Fido and FidoNet are registered marks of Tom Jennings and Fido
  21.      Software.
  22.  
  23.  
  24.  
  25.  
  26. This document is written by :
  27.  
  28.     Frank van der Loos
  29.     Torenstraat 123
  30.     3311 TR Dordrecht
  31.     The Netherlands (Europe)
  32.     FIDO mail : 2:285/305.4
  33.  
  34. Thanx to :
  35.     Willem van Pelt
  36.     FIDO mail : 2:285/305
  37.     - for giving me a mail-box :-))
  38.     - for telling me some theoretical stuff about CRC's
  39.  
  40.     Richard Faasen (Yeaahh "Pfjew" he says)
  41.     FIDO mail : 2:285/311
  42.     - for giving me some CRC programs
  43.  
  44.     Arie Ballegooyen
  45.     FIDO mail : 2:283/300
  46.     - for giving me all the original FTS & FSC doc's
  47.  
  48.  
  49.  
  50. This doument is a DOC in which the CRC encoding and some usages of this
  51. encoding are explained. Also some routines are included. In some of the
  52. FTS & FTC doc's the encoding is very badly and sometimes wrong explained
  53. this will take a lot of time when you are planning to program a CRC encoding
  54. routine instead of using a routine which is made by someone. I will also
  55. include some routines and also the scheme to make a CRC routine so you
  56. can easily make a CRC check routine yourself in your program.
  57.  
  58. What is a CRC :
  59.  
  60. Simply explained a CRC is a division and the remainder is the CRC value.
  61. I think this example will help you to understand it :
  62.  
  63. 1011 / 10011101 \
  64.        1011
  65.        ----
  66.          1011
  67.          1011
  68.          ----
  69.             001 (This is the CRC value)
  70.  
  71. Look familiar to division as you are used to learn at school. But there
  72. are some differences.
  73.  
  74. When substracting a bit the following table is used :
  75. 0 - 0 = 0
  76. 0 - 1 = 1
  77. 1 - 0 = 1
  78. 1 - 1 = 0
  79.  
  80. There is a function called XOR which will use this table. When you are
  81. substracting 0-1 = 1 then there is a shortage and normally you will take
  82. a higher bit to complete to substraction.
  83.  
  84. 234
  85.  91 -
  86. -----
  87. 143
  88.  
  89. You cutted 200 to 100 because 3-9 = negative. But with the CRC you
  90. DO NOT use this !!!
  91.  
  92. The divisor used with CRC encoding is a divisor with 1 bit more then
  93. de actual CRC. This is explained by the remainder which is always 1 bit
  94. less then the divisor. If not then you can divide it a time again, not ?
  95.  
  96. Now you have to perform dividing on a row of char's and you can't do that
  97. without a special trick. What you do is shifting all the bits one by one
  98. into the CRCvalue and then checking if you can perform a division. Lets
  99. have a look at this example :
  100.  
  101. 1011 / 10011101 \
  102.  
  103. We are gonna use a CRC of 3 bits (the highest bit is always cutted).
  104. The first bit is the checkbit. We can divide if this bit is 1. In that
  105. case the value is big enough to divide.
  106.  
  107.  
  108.    x 100 no we can not divide
  109.     perform a shift to left and shift in the next bit.
  110.    1 001 yes we can divide
  111.      divide it by 1011
  112.    0 010 the divided value (XOR'ed)
  113.          we can not divide so shift to left and shift in the next bit.
  114.    0 101 the shifted value + shifted bit.
  115.          we can not divide so shift to left and shift in the next bit.
  116.    1 011 the shifted value + shifted bit.
  117.          divide it by 1011
  118.    0 000 the divied value (XOR'ed)
  119.          we can not divide it so shift to left and shift in the next bit.
  120.    0 000 the shifted value + shifted bit.
  121.          we can not divide it so shift to left and shift in the next bit.
  122.    0 001 the shifted value + shifted bit.
  123.          we can not divide it so shift to left and shift in the next bit.
  124.          OOOppps sorry the bits are gone so this is the remainder
  125.      001 The 3 bit remainder (is 1 less then the divisor)
  126.  
  127.  
  128.   0 101 no we can not divide so
  129.     no we can not divide
  130.     shift to left and take the next bit.
  131.    1 011 yes we can divide
  132.    0 000 the divided value (XOR'ed)
  133.    0 001 oke we have shifted again to left and took again the next
  134.      bit.
  135.    0 010 again
  136.    0 101 again
  137.  
  138. Compare it to the division performed at page 1 and you will see the result
  139. is the same. But this method is more comfortable for computers. In fact
  140. it is the same way to divide but we as humans can take more bits and we
  141. can see direct if it is possible to divide and the computer can not. But if
  142. we have to check every bit it will take a lot of time to put in every time
  143. 1 bit by bit. Now luckily for you that is not neccesairy. The computer and
  144. also your program can shift in byte per byte. But then you have to try the
  145. division 8 times every time you have putted in a byte. And the byte you have
  146. put in has to fit in your CRC. So when you have a CRC which is 2 bits in
  147. length than it won't fit of course. Bu generally a 16 bit CRC is used and
  148. even CRC32 are now in use. When in the near future CRC64 are used I'm not
  149. surprised. Oke now to the computuer programming stuff. Here is a table with
  150. a good method to implement a CRC16 in any language. After this a program
  151. is stated with all the documentation in it. Remember a CRC16 has a 17bit
  152. divisor. Bit 16 (As you know we start at bit 0) is 1. When not we have again
  153.  a smaller divisor.
  154.  
  155. CRC : wordvalue
  156.  
  157. { This routine has to be executed 8 times }
  158. IF CRC bit 15 = 1
  159. then
  160. shift left 1, divide by divisor (16 bits)
  161. else
  162. shift left 1, {do not divide cause we can't}
  163.  
  164. {After this put in the next byte}
  165. CRC = CRC + inputbyte
  166.  
  167. {end of this routine}
  168.  
  169. Simple isn't it. Now for the more experienced programmers a sample in
  170. pascal at the next page.
  171.  
  172.  
  173. inpbyte = input byte for CRC
  174. oldCRC = old crc value
  175. divisor = the least 16 bits of the divisor string
  176.  
  177. Function CRC16 ( inpbyte : byte, oldCRC : word, divisor : word ) : word ;
  178.  
  179. var
  180. tel : word;
  181. temp : word;  {A simple variable to use to store the CRC)
  182.  
  183. begin
  184. temp := oldCRC;
  185. for tel := 1 to 8 do
  186. begin
  187.  
  188.   If (temp and $8000)= $8000
  189.   then
  190.     begin
  191.       temp := temp shl 1;
  192.       temp := temp xor divisor;
  193.     end
  194.   else
  195.     begin
  196.       temp := temp shl 1;
  197.     end;
  198.  
  199.   { Now we have to put in the next byte }
  200.  
  201.   temp := temp xor inpbyte;
  202.  
  203.   CRC16 := temp;
  204.  
  205. end;
  206.  
  207. {End of routine}
  208.  
  209. This routine is easily to expand to CRC32. In that case you have to expand
  210. your divisor and temp and CRC function to LONG value's.
  211.  
  212. Some additional information about CRC's :
  213.  
  214. CRC16 divisor =  $1021 ( + bit 16 = $3021 )
  215. The CRC16 feed value (when you first call the CRC routine) is $0000
  216. CRC32 divisor =  $77073096 ( + bit 32 = $17707306 )
  217. The CRC32 feed value (when you first call the CRC routine) is $FFFFFFFF
  218.